package graphlib;

// PairHeap class

import java.util.*;


/**
 * Generic implementation of the Parring Heap datastructure for PriorityQuee
 * Supports a decreaseKey operation.
 * @author KF04-ITU-2011, Group 11
 * @see PairNode
 */
public class PairHeap<T>
{
    // The tree array for combineSiblings
    private PairNode<T> [ ] treeArray;
    private PairNode root;
    private HashMap<T,PairNode<T>> nodes;
    private Comparator c;

    /**
     * Construct the pairing heap.
     */
    public PairHeap( int initCapacity, Comparator<T> c )
    {
        root = null;
        treeArray = new PairNode[initCapacity];
        nodes = new HashMap<T,PairNode<T>>();
        this.c = c;
    }

    /**
     * Insert into the priority queue, and return a PairNode
     * that can be used by decreaseKey.
     * Duplicates are allowed.
     * @param x the item to insert.
     * @return the node containing the newly inserted item.
     */
    public PairNode insert( T x )
    {
        PairNode newNode = new PairNode( x );
        nodes.put(x,newNode);

        if( root == null )
            root = newNode;
        else
            root = compareAndLink( root, newNode );
        return newNode;
    }

    /**
     * Find the smallest item in the priority queue.
     * @return the smallest item, or null if empty.
     */
    public T findMin( )
    {
        if( isEmpty( ) )
            return null;
        return (T) root.element;
    }

    /**
     * Remove the smallest item from the priority queue.
     * @return the smallest item, or null if empty.
     */
    public T deleteMin( )
    {
        if( isEmpty( ) )
            return null;

        T x = findMin( );
        if( root.leftChild == null )
            root = null;
        else
            root = combineSiblings( root.leftChild );

        return x;
    }

    /**
     * Change the value of the item stored in the pairing heap.
     * Does nothing if newVal is larger than the currently stored value.
     * @param p any node returned by addItem.
     * @param newVal the new value, which must be smaller
     *    than the currently stored value.
     */
    public void updateDecreasedObject( T object )
    {
        PairNode p = nodes.get(object);
        if(p==null) return;
        if( p != root )
        {
            if( p.nextSibling != null )
                p.nextSibling.prev = p.prev;
            if( p.prev.leftChild == p )
                p.prev.leftChild = p.nextSibling;
            else
                p.prev.nextSibling = p.nextSibling;

            p.nextSibling = null;
            root = compareAndLink( root, p );
        }
    }

    public void updateDecreasedObject( T object, T newObject )
    {
        PairNode p = nodes.get(object);
        if(p==null) return;
        p.element = newObject;
        if( p != root )
        {
            if( p.nextSibling != null )
                p.nextSibling.prev = p.prev;
            if( p.prev.leftChild == p )
                p.prev.leftChild = p.nextSibling;
            else
                p.prev.nextSibling = p.nextSibling;

            p.nextSibling = null;
            root = compareAndLink( root, p );
        }
    }

    public boolean contains(T object){
        return nodes.containsKey(object);
    }

    /**
     * Test if the priority queue is logically empty.
     * @return true if empty, false otherwise.
     */
    public boolean isEmpty( )
    {
        return root == null;
    }

    /**
     * Make the priority queue logically empty.
     */
    public void makeEmpty( )
    {
        root = null;
    }


    /**
     * Internal method that is the basic operation to maintain order.
     * Links first and second together to satisfy heap order.
     * @param first root of tree 1, which may not be null.
     *    first.nextSibling MUST be null on entry.
     * @param second root of tree 2, which may be null.
     * @return result of the tree merge.
     */
    private PairNode compareAndLink( PairNode first, PairNode second )
    {
        if( second == null )
            return first;

        if(c.compare(second.element, first.element ) < 0 )
        {
            // Attach first as leftmost child of second
            second.prev = first.prev;
            first.prev = second;
            first.nextSibling = second.leftChild;
            if( first.nextSibling != null )
                first.nextSibling.prev = first;
            second.leftChild = first;
            return second;
        }
        else
        {
            // Attach second as leftmost child of first
            second.prev = first;
            first.nextSibling = second.nextSibling;
            if( first.nextSibling != null )
                first.nextSibling.prev = first;
            second.nextSibling = first.leftChild;
            if( second.nextSibling != null )
                second.nextSibling.prev = second;
            first.leftChild = second;
            return first;
        }
    }

    private PairNode [ ] doubleIfFull( PairNode [ ] array, int index )
    {
        if( index == array.length )
        {
            PairNode [ ] oldArray = array;
            array = new PairNode[ index * 2 ];
            for( int i = 0; i < index; i++ )
                array[ i ] = oldArray[ i ];
        }
        return array;
    }


    /**
     * Internal method that implements two-pass merging.
     * @param firstSibling the root of the conglomerate;
     *     assumed not null.
     */
    private PairNode combineSiblings( PairNode firstSibling )
    {
        if( firstSibling.nextSibling == null )
            return firstSibling;

            // Store the subtrees in an array
        int numSiblings = 0;
        for( ; firstSibling != null; numSiblings++ )
        {
            treeArray = doubleIfFull( treeArray, numSiblings );
            treeArray[ numSiblings ] = firstSibling;
            firstSibling.prev.nextSibling = null;  // break links
            firstSibling = firstSibling.nextSibling;
        }
        treeArray = doubleIfFull( treeArray, numSiblings );
        treeArray[ numSiblings ] = null;

            // Combine subtrees two at a time, going left to right
        int i = 0;
        for( ; i + 1 < numSiblings; i += 2 )
            treeArray[ i ] = compareAndLink( treeArray[ i ], treeArray[ i + 1 ] );

        int j = i - 2;

            // j has the result of last compareAndLink.
            // If an odd number of trees, get the last one.
        if( j == numSiblings - 3 )
            treeArray[ j ] = compareAndLink( treeArray[ j ], treeArray[ j + 2 ] );

            // Now go right to left, merging last tree with
            // next to last. The result becomes the new last.
        for( ; j >= 2; j -= 2 )
            treeArray[ j - 2 ] = compareAndLink( treeArray[ j - 2 ], treeArray[ j ] );

        return treeArray[ 0 ];
    }

    public static void main(String[] args){
        PairHeap<Integer> p = new PairHeap<Integer>(1000, new Comparator<Integer>() {
            public int compare(Integer o1, Integer o2)
            {
                return o1.compareTo(o2);
            }
        });
        int j = 0;
        for(int i = 0; i<1000; i++){
            j += (int) Math.floor(Math.random()*20);
            p.insert(j);
        }
        for(int i = 5000; i<100000; i++){
            p.updateDecreasedObject(i, 25);
        }
        for(int i = 0; i<1000; i++){
            System.out.println(p.deleteMin());
        }
        System.out.println(p.isEmpty()+"");
    }

    /**
     * Data class for pair node
     * @param <T> The datatype for the element
     */
    private class PairNode<T>
    {
        /**
         * Construct the PairNode.
         * @param theElement the value stored in the node.
         */
        PairNode( T theElement )
        {
            element     = theElement;
            leftChild   = null;
            nextSibling = null;
            prev        = null;
        }

            // Friendly data; accessible by other package routines
        T element;
        PairNode   leftChild;
        PairNode   nextSibling;
        PairNode   prev;
    }

}
